// ml:run = $bin < input
// ml:opt = 0
// ml:ccf += -g
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <limits>
#include <queue>

template <class T>
struct dinic
{
	typedef T value_type;
	typedef long long size_type;
	typedef std::vector<size_type>::iterator edge_iter;

	struct edge {
		size_type from, to;
		value_type capacity, flow;
	};

	dinic(size_type num) : size(num)
	{
		graph.resize(num);	//[0, num)
		dist.resize(num);	//[0, num)
	}

	void add_edge(long long u, long long v, value_type cap = capacity_inf)
	{
		edge tmp;
		tmp.from = u; tmp.to = v; tmp.capacity = cap; tmp.flow = 0;
		edges.push_back(tmp);
		graph[u].push_back(edges.size() - 1);

		tmp.from = v; tmp.to = u; tmp.capacity = 0; tmp.flow = 0;
		edges.push_back(tmp);
		graph[v].push_back(edges.size() - 1);
	}

	bool bfs_label(size_type source, size_type target)
	{
		std::fill(dist.begin(), dist.end(), -1);
		std::queue<size_type> q;
		q.push(source);
		dist[source] = 0;
		while (!q.empty()) {
			size_type now = q.front();
			q.pop();
			for (edge_iter it = graph[now].begin(); it != graph[now].end(); ++it) {
				edge e = edges[*it];
				if (dist[e.to] == -1 && e.capacity > e.flow) {
					q.push(e.to);
					dist[e.to] = dist[now] + 1;
				}
			}
		}
		return dist[target] != -1;
	}

	value_type dfs(size_type v, size_type target, value_type f)
	{
		if (v == target || !f) return f;
		value_type block_flow = 0;
		for (edge_iter it = graph[v].begin(); it != graph[v].end(); ++it) {
			edge & e = edges[*it];
			if (e.capacity > e.flow && dist[e.to] == dist[v] + 1) {
				value_type tmp = dfs(e.to, target,
						std::min(e.capacity - e.flow, f - block_flow));
				block_flow += tmp;
				e.flow += tmp;
				edges[(*it) ^ 1].flow -= tmp;
			}
		}
		if (!block_flow) dist[v] = -1;
		return block_flow;
	}

	value_type max_flow(size_type source, size_type target)
	{
		value_type flow = 0;
		for (long long tmp; bfs_label(source, target); )
			while ((tmp = dfs(source, target, capacity_inf))) flow += tmp;
		return flow;
	}

//private:
	value_type static const capacity_inf = (1ll) << 44;
	size_type size;
	std::vector<long long> dist;
	std::vector<edge> edges;
	std::vector<std::vector<size_type>> graph;
};

long long const maxn = 2007;
long long const maxm = 20070;
long long const  inf = (1ll) << 44;

struct edge { long long from, to, cost, id; };

std::vector<std::vector<edge>> graph;
bool vis_edge[maxm];
bool vis[maxn];
long long dist[maxn];
std::vector<edge> edges;
long long n, m;

void init()
{
    for (long long i = 1; i <= n; i++) {
        dist[i] = inf;
        vis[i] = false;
    }
    std::memset(vis_edge, 0, sizeof(vis_edge));
    graph.clear();
    graph.resize(n + 1);
}

void add_edge(long long u, long long v, long long w, long long id)
{
    graph[u].push_back({u, v, w, id});
    graph[v].push_back({v, u, w, id});
}

int main()
{
    std::ios::sync_with_stdio(false);
    long long T; std::cin >> T;
    while (T--) {
        std::cin >> n >> m;
        init();
        edges.resize(m);
        for (long long i = 0; i < m; i++) {
            long long u, v, w; std::cin >> u >> v >> w;
            edges[i] = {u, v, w, i};
            add_edge(u, v, w, i);
        }

        std::queue<long long> q;
        dist[1] = 0;
        q.push(1);
        vis[1] = true;
        while (!q.empty()) {
            auto now = q.front(); q.pop();
            for (auto e : graph[now]) {
                if (vis[e.to]) continue;
                vis[e.to] = true;
                q.push(e.to);
                dist[e.to] = dist[now] + 1;
            }
        }
        if (dist[n] >= inf) {
            std::cout << "0\n";
            continue;
        }

        for (long long i = 1; i <= n; i++) {
            for (auto e : graph[i])
                if (dist[i] + 1 == dist[e.to]) {
                    vis_edge[e.id] = true;
                    if (edges[e.id].from != i)
                        std::swap(edges[e.id].from, edges[e.id].to);
                }
        }

        long long source = 1, target = n;
        dinic<long long> d(n + 4);
        for (auto e : edges) {
            if (!vis_edge[e.id]) continue;
            d.add_edge(e.from, e.to, e.cost);
            /* std::cout << e.from << " " << e.to << " " << e.cost << "\n"; */
        }
        std::cout << d.max_flow(source, target) << "\n";
    }
}

